#pragma once
/***
 *  线性表 c语言实现（链表）
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>
/***
 * 抽象数据类型线性表定义
 * ADT List{
 * 数据对象：D
 * 数据关系：R1
 * 基本操作：
 * Status MakeNode(Link&p,ElemType e);
 * //分配由p指向的值为e的结点，并返回ok；若分配失败，则返回ERROR;
 * void FreeNode(Link&p);
 * //释放p所指的结点
 * status InitList(LinkList &L);
 * //构造一个空的线性链表
 * status ClearList(LinkList &L);
 * //重置为空表
 * status InsFirst(Link h,Link s);
 * //已知h 指向线性链表的头结点，将s所指的结点插入在第一个结点之前
 *  status DelFirst(Link h,Link s);
 * //已知h 指向线性链表的头结点，删除链表中的第一个结点并以q返回
 * status Append(LinkList&l,Link s);
 * //将指针s所指的一串结点链接在线性链表L的最后一个结点
 * Status Remove(LinkList&l,Link q)
 * //删除链表中的尾结点并以q返回
 * 
 *  Status InsBefore(LinkList&l,Link q，Link s)
 * //将s所指的结点插入在p结点之前
 *  Status InsAfter(LinkList&l,Link q，Link s)
 * ///将s所指的结点插入在p结点之后
 *  Status setCurElem(Link q，ElemType e)
 * //设置结点中的元素
 *  ElemType getCurElem(Link q)
 * //获取结点中的元素
 *  Status ListEmpty(LinkList&l)
 * //判断链表是否为空
 *  Status ListLength(LinkList&l)
 *  //返回链表长度
 *  Status GetHead(LinkList&l,Link q)
 * //返回 链表l 中头结点
 *  status GetLast(LinkList&l)
 * //返回 链表l 中尾结点
 *  status PriorPos(LinkList&l,Link q)
 * //返回 链表l 中q节点的前一个节点
 *  status NextPos((LinkList&l,Link q)
 * //返回 链表l 中q节点的下一个节点
 *  status LocatePos(LinkList&l,int i,Link q)
 * //返回p指示线性链表L中的第i个结点
 *  position LocateElem(LinkList&l,ElemType e)
 *  返回线性链表中第一个和元素e相等的位置
 *  status ListTraverse(LinkList&l,Link q)
 * //遍历链表
 */
typedef int ElemType;

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} *Link;

typedef struct {
    Link head, tail; // 头指针、尾指针
    int len;         // 当前链表长度
} LinkList;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define Status int

Status MakeNode(Link *p, ElemType e) {
    *p = (Link)malloc(sizeof(struct LNode));
    if (!*p)
        return ERROR; // 分配失败
    (*p)->data = e;
    (*p)->next = NULL;
    return OK;
}

void FreeNode(Link *p) {
    free(*p);
    *p = NULL;
}

Status InitList(LinkList *L) {
    L->head = (Link)malloc(sizeof(struct LNode)); // 创建头结点
    if (!L->head)
        return ERROR;
    L->tail = L->head;
    L->len = 0;
    L->head->next = NULL;
    return OK;
}

//删除结点h的头结点，并赋值q 111
Status DelFirst(LinkList *L, Link h, Link *q) {
    if (h->next == NULL) 
        return ERROR;
    
    *q = h->next;
    h->next = (*q)->next;
    
    if (*q == L->tail)  // 若删除尾节点
        L->tail = h;
    
    (*q)->next = NULL;
    L->len--;
    return OK;
}


Status ListEmpty(LinkList *L) {
    return (L->len == 0) ? OK : ERROR;
}

int ListLength(LinkList *L) {
    return L->len;
}

Status SetCurElem(Link q, ElemType e) {
    if (!q)
        return ERROR;
    q->data = e;
    return OK;
}

ElemType GetCurElem(Link q) {
    return q->data;
}

Status LocatePos(LinkList *L, int i, Link *q) {
    if (i < 1 || i > L->len) 
        return ERROR;  // 位置非法
    
    Link p = L->head->next;  // 首元节点
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) 
        return ERROR;
    
    *q = p;
    return OK;
}

Link LocateElem(LinkList *L, ElemType e, 
               Status (*compare)(ElemType, ElemType)) 
{
    Link p = L->head->next;
    while (p) {
        if (compare(e, p->data)) 
            return p;
        p = p->next;
    }
    return NULL;  // 未找到
}

// 示例比较函数：
Status isEqual(ElemType a, ElemType b) {
    return a == b;
}

//在链表L中的节点q前增加结点s，111
Status InsBefore(LinkList *L, Link *q, Link s) {
    if (!*q || *q == L->head) 
        return ERROR;  // q为头节点或空
    
    // 查找q的前驱节点
    Link pre = L->head;
    while (pre->next && pre->next != *q) 
        pre = pre->next;
    
    if (!pre->next) 
        return ERROR;  // q不在链表中
    
    s->next = *q;
    pre->next = s;
    
    if (*q == L->head->next)  // 若插入在首元节点前
        L->head->next = s;
    
    L->len++;
    return OK;
}

//在链表L中的节点q后增加结点s，111
Status InsAfter(LinkList *L, Link *q, Link s) {
    if (!*q) return ERROR;
    
    s->next = (*q)->next;
    (*q)->next = s;
    
    if (*q == L->tail)  // 若插入在尾节点后
        L->tail = s;
    
    L->len++;
    return OK;
}

/// @brief 链表L尾部插入结点s ，111
/// @param L 
/// @param s 
/// @return 
Status Append(LinkList *L, Link s) {
    L->tail->next = s;    //1.当前的尾结点的next给到s
    while (s->next) {  // 找到新链表的尾节点
        s = s->next;
        L->len++;
    }
    L->tail = s;     //2.将s的最后一个结点赋值给尾结点
    L->len++;
    return OK;
}

//删除链表l中的结点q
Status Remove(LinkList *L, Link *q, ElemType *e) {
    if (!*q || *q == L->head) 
        return ERROR;
    
    // 查找前驱节点
    Link pre = L->head;
    while (pre->next && pre->next != *q) 
        pre = pre->next;
    
    if (!pre->next) 
        return ERROR;
    
    pre->next = (*q)->next;
    *e = (*q)->data;
    
    if (*q == L->tail)  // 若删除尾节点
        L->tail = pre;
    
    FreeNode(q);
    L->len--;
    return OK;
}

Status ClearList(LinkList *L) {
    Link p;
    while (L->head->next) {
        DelFirst(L, L->head, &p);
        FreeNode(&p);
    }
    L->tail = L->head;
    L->len = 0;
    return OK;
}

Status ListTraverse(LinkList *L, Status (*visit)(Link)) {
    Link p = L->head->next;
    while (p) {
        if (!visit(p)) 
            return ERROR;
        p = p->next;
    }
    return OK;
}

// 示例访问函数：
Status printNode(Link p) {
    printf("%d ", p->data);
    return OK;
}

Status DestroyList(LinkList *L) {
    ClearList(L);
    FreeNode(&(L->head));  // 释放头节点
    L->tail = NULL;
    L->len = 0;
    return OK;
}